package Sort;

/**
 * TOOD
 *
 * @author long
 * @date 2020-07-26 17:12
 */
public class xierSort {

    public static  int[] xierSort(int[] arr){
      /* //i层循环控制步长
        for (int i=arr.length/2;i>0;i/=2){
            //j控制无序端的起始位置
            for (int j=i;j<arr.length;j++){
                for (int k=j;k>0&&k-i>=0;k-=i){
                    if (arr[k]<arr[k-i]){
                        int temp=arr[k-i];
                        arr[k-i]=arr[k];
                        arr[k]=temp;
                    }else {
                        break;
                    }
                }
                //j k 为插入排序，不过步长为i；
            }
        }*/
   for (int i=arr.length/2;i>0;i/=2){
       for (int j=i;j<arr.length;j++){
           for (int k=j;k>0&&k-i>=0;k-=i){
               if (arr[k]<arr[k-i]){
                   int temp=arr[k-i];
                   arr[k-i]=arr[k];
                   arr[k]=temp;
               }else {
                   break;
               }
           }
       }
   }

        return arr;
    }


    public static  void  main(String[] args){
        int arr[]={8,5,3,9,10,12,1};
        int[] ints = xierSort(arr);
       for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }
}
